<!DOCTYPE html>
<html>
<head>
<title>实验七.md</title>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">

<style>
/*

Arduino® Light Theme - Stefania Mellai <s.mellai@arduino.cc>

*/

.hljs {
  display: block;
  overflow-x: auto;
  padding: 0.5em;
  background: #FFFFFF;
}

.hljs,
.hljs-subst {
  color: #434f54;
}

.hljs-keyword,
.hljs-attribute,
.hljs-selector-tag,
.hljs-doctag,
.hljs-name {
  color: #00979D;
}

.hljs-built_in,
.hljs-literal,
.hljs-bullet,
.hljs-code,
.hljs-addition {
  color: #D35400;
}

.hljs-regexp,
.hljs-symbol,
.hljs-variable,
.hljs-template-variable,
.hljs-link,
.hljs-selector-attr,
.hljs-selector-pseudo {
  color: #00979D;
}

.hljs-type,
.hljs-string,
.hljs-selector-id,
.hljs-selector-class,
.hljs-quote,
.hljs-template-tag,
.hljs-deletion {
  color: #005C5F;
}

.hljs-title,
.hljs-section {
  color: #880000;
  font-weight: bold;
}

.hljs-comment {
  color: rgba(149,165,166,.8);
}

.hljs-meta-keyword {
  color: #728E00;
}

.hljs-meta {
  color: #434f54;
}

.hljs-emphasis {
  font-style: italic;
}

.hljs-strong {
  font-weight: bold;
}

.hljs-function {
  color: #728E00;
}

.hljs-number {
  color: #8A7B52;  
}

</style>

<style>
/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

body {
	font-family:   "HelveticaNeue-Light", sans-serif, "宋体","Segoe WPC", "Segoe UI", "SFUIText-Light","Droid Sans Fallback";
	font-size: 18px;
	padding: 0 12px;
	line-height: 1.6;
	word-wrap: break-word;
	color: #333333;
}

.content-wrapper{
	max-width: 860px;
    margin: 0 auto;
    padding: 0 30px;
}

#code-csp-warning {
	position: fixed;
	top: 0;
	right: 0;
	color: white;
	margin: 16px;
	text-align: center;
	font-size: 12px;
	font-family: sans-serif;
	background-color:#444444;
	cursor: pointer;
	padding: 6px;
	box-shadow: 1px 1px 1px rgba(0,0,0,.25);
}

#code-csp-warning:hover {
	text-decoration: none;
	background-color:#007acc;
	box-shadow: 2px 2px 2px rgba(0,0,0,.25);
}


body.scrollBeyondLastLine {
	margin-bottom: calc(100vh - 22px);
}

body.showEditorSelection .code-line {
	position: relative;
}

body.showEditorSelection .code-active-line:before,
body.showEditorSelection .code-line:hover:before {
	content: "";
	display: block;
	position: absolute;
	top: 0;
	left: -12px;
	height: 100%;
}

body.showEditorSelection li.code-active-line:before,
body.showEditorSelection li.code-line:hover:before {
	left: -30px;
}

.vscode-light.showEditorSelection .code-active-line:before {
	border-left: 3px solid rgba(0, 0, 0, 0.15);
}

.vscode-light.showEditorSelection .code-line:hover:before {
	border-left: 3px solid rgba(0, 0, 0, 0.40);
}

.vscode-dark.showEditorSelection .code-active-line:before {
	border-left: 3px solid rgba(255, 255, 255, 0.4);
}

.vscode-dark.showEditorSelection .code-line:hover:before {
	border-left: 3px solid rgba(255, 255, 255, 0.60);
}

.vscode-high-contrast.showEditorSelection .code-active-line:before {
	border-left: 3px solid rgba(255, 160, 0, 0.7);
}

.vscode-high-contrast.showEditorSelection .code-line:hover:before {
	border-left: 3px solid rgba(255, 160, 0, 1);
}

img {
	max-width: 100%;
	max-height: 100%;
}

a {
	color: #4080D0;
	text-decoration: none;
}

a:focus,
input:focus,
select:focus,
textarea:focus {
	outline: 1px solid -webkit-focus-ring-color;
	outline-offset: -1px;
}

hr {
	border: 0;
	height: 2px;
	border-bottom: 2px solid;
}

h1 {
	padding-bottom: 0.3em;
	line-height: 1.2;
	border-bottom: 1px solid #eee;
}


h2{
	padding-bottom: .3em;
    font-size: 2em;
    line-height: 1.225;
    border-bottom: 1px solid #eee;
}

h3{
	font-size: 1.75em;
    line-height: 1.225;
}

h1, h2, h3 {
	font-weight: bold;
}

h1 code,
h2 code,
h3 code,
h4 code,
h5 code,
h6 code {
	font-size: inherit;
	line-height: auto;
}

a:hover {
	color: #4080D0;
	text-decoration: underline;
}

table {
	border-collapse: collapse;
}

table > thead > tr > th {
	text-align: left;
	border-bottom: 1px solid;
}

table > thead > tr > th,
table > thead > tr > td,
table > tbody > tr > th,
table > tbody > tr > td {
	padding: 5px 10px;
}

table > tbody > tr + tr > td {
	border-top: 1px solid;
}

blockquote {
	margin: 0 7px 0 5px;
	padding: 0 16px 0 10px;
	border-left: 5px solid;
}

code {
	font-family: Menlo, Monaco, Consolas, "Droid Sans Mono", "Courier New", monospace, "Droid Sans Fallback";
	font-size: 14px;
	line-height: 19px;
}

body.wordWrap pre {
	white-space: pre-wrap;
}

.mac code {
	font-size: 12px;
	line-height: 18px;
}

pre:not(.hljs),
pre.hljs code > div {
	padding: 16px;
	border-radius: 3px;
	overflow: auto;
}

/** Theming */

.vscode-light,
.vscode-light pre code {
	color: rgb(30, 30, 30);
}

.vscode-dark,
.vscode-dark pre code {
	color: #DDD;
}

.vscode-high-contrast,
.vscode-high-contrast pre code {
	color: white;
}

.vscode-light code {
	color: #A31515;
}

.vscode-dark code {
	color: #D7BA7D;
}

.vscode-light pre:not(.hljs),
.vscode-light code > div {
	background-color: rgba(220, 220, 220, 0.4);
}

.vscode-dark pre:not(.hljs),
.vscode-dark code > div {
	background-color: rgba(10, 10, 10, 0.4);
}

.vscode-high-contrast pre:not(.hljs),
.vscode-high-contrast code > div {
	background-color: rgb(0, 0, 0);
}

.vscode-high-contrast h1 {
	border-color: rgb(0, 0, 0);
}

.vscode-light table > thead > tr > th {
	border-color: rgba(0, 0, 0, 0.69);
}

.vscode-dark table > thead > tr > th {
	border-color: rgba(255, 255, 255, 0.69);
}

.vscode-light h1,
.vscode-light hr,
.vscode-light table > tbody > tr + tr > td {
	border-color: rgba(0, 0, 0, 0.18);
}

.vscode-dark h1,
.vscode-dark hr,
.vscode-dark table > tbody > tr + tr > td {
	border-color: rgba(255, 255, 255, 0.18);
}

.vscode-light blockquote,
.vscode-dark blockquote {
	background: rgba(127, 127, 127, 0.1);
	border-color: rgba(0, 122, 204, 0.5);
}

.vscode-high-contrast blockquote {
	background: transparent;
	border-color: #fff;
}
</style>

<style>
pre {
	background-color: #f8f8f8;
	border: 1px solid #cccccc;
	border-radius: 3px;
	overflow-x: auto;
	white-space: pre-wrap;
	overflow-wrap: break-word;
}

pre:not(.hljs) {
	padding: 23px;
	line-height: 19px;
}

blockquote {
	background: rgba(127, 127, 127, 0.1);
	border-color: rgba(0, 122, 204, 0.5);
}

.emoji {
	height: 1.4em;
}

/* for inline code */
:not(pre):not(.hljs) > code {
	color: #C9AE75; /* Change the old color so it seems less like an error */
	font-size: inherit;
}

/* Page Break : use <div class="page"/> to insert page break
-------------------------------------------------------- */
.page {
	page-break-after: always;
}

.table-of-contents li{
	list-style-type: initial;
}
</style>

<style>
@font-face{font-family:KaTeX_AMS;font-style:normal;font-weight:400;src:url(fonts/KaTeX_AMS-Regular.woff2) format("woff2"),url(fonts/KaTeX_AMS-Regular.woff) format("woff"),url(fonts/KaTeX_AMS-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Caligraphic;font-style:normal;font-weight:700;src:url(fonts/KaTeX_Caligraphic-Bold.woff2) format("woff2"),url(fonts/KaTeX_Caligraphic-Bold.woff) format("woff"),url(fonts/KaTeX_Caligraphic-Bold.ttf) format("truetype")}@font-face{font-family:KaTeX_Caligraphic;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Caligraphic-Regular.woff2) format("woff2"),url(fonts/KaTeX_Caligraphic-Regular.woff) format("woff"),url(fonts/KaTeX_Caligraphic-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Fraktur;font-style:normal;font-weight:700;src:url(fonts/KaTeX_Fraktur-Bold.woff2) format("woff2"),url(fonts/KaTeX_Fraktur-Bold.woff) format("woff"),url(fonts/KaTeX_Fraktur-Bold.ttf) format("truetype")}@font-face{font-family:KaTeX_Fraktur;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Fraktur-Regular.woff2) format("woff2"),url(fonts/KaTeX_Fraktur-Regular.woff) format("woff"),url(fonts/KaTeX_Fraktur-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:normal;font-weight:700;src:url(fonts/KaTeX_Main-Bold.woff2) format("woff2"),url(fonts/KaTeX_Main-Bold.woff) format("woff"),url(fonts/KaTeX_Main-Bold.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:italic;font-weight:700;src:url(fonts/KaTeX_Main-BoldItalic.woff2) format("woff2"),url(fonts/KaTeX_Main-BoldItalic.woff) format("woff"),url(fonts/KaTeX_Main-BoldItalic.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:italic;font-weight:400;src:url(fonts/KaTeX_Main-Italic.woff2) format("woff2"),url(fonts/KaTeX_Main-Italic.woff) format("woff"),url(fonts/KaTeX_Main-Italic.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Main-Regular.woff2) format("woff2"),url(fonts/KaTeX_Main-Regular.woff) format("woff"),url(fonts/KaTeX_Main-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Math;font-style:italic;font-weight:700;src:url(fonts/KaTeX_Math-BoldItalic.woff2) format("woff2"),url(fonts/KaTeX_Math-BoldItalic.woff) format("woff"),url(fonts/KaTeX_Math-BoldItalic.ttf) format("truetype")}@font-face{font-family:KaTeX_Math;font-style:italic;font-weight:400;src:url(fonts/KaTeX_Math-Italic.woff2) format("woff2"),url(fonts/KaTeX_Math-Italic.woff) format("woff"),url(fonts/KaTeX_Math-Italic.ttf) format("truetype")}@font-face{font-family:"KaTeX_SansSerif";font-style:normal;font-weight:700;src:url(fonts/KaTeX_SansSerif-Bold.woff2) format("woff2"),url(fonts/KaTeX_SansSerif-Bold.woff) format("woff"),url(fonts/KaTeX_SansSerif-Bold.ttf) format("truetype")}@font-face{font-family:"KaTeX_SansSerif";font-style:italic;font-weight:400;src:url(fonts/KaTeX_SansSerif-Italic.woff2) format("woff2"),url(fonts/KaTeX_SansSerif-Italic.woff) format("woff"),url(fonts/KaTeX_SansSerif-Italic.ttf) format("truetype")}@font-face{font-family:"KaTeX_SansSerif";font-style:normal;font-weight:400;src:url(fonts/KaTeX_SansSerif-Regular.woff2) format("woff2"),url(fonts/KaTeX_SansSerif-Regular.woff) format("woff"),url(fonts/KaTeX_SansSerif-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Script;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Script-Regular.woff2) format("woff2"),url(fonts/KaTeX_Script-Regular.woff) format("woff"),url(fonts/KaTeX_Script-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size1;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size1-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size1-Regular.woff) format("woff"),url(fonts/KaTeX_Size1-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size2;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size2-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size2-Regular.woff) format("woff"),url(fonts/KaTeX_Size2-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size3;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size3-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size3-Regular.woff) format("woff"),url(fonts/KaTeX_Size3-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size4;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size4-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size4-Regular.woff) format("woff"),url(fonts/KaTeX_Size4-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Typewriter;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Typewriter-Regular.woff2) format("woff2"),url(fonts/KaTeX_Typewriter-Regular.woff) format("woff"),url(fonts/KaTeX_Typewriter-Regular.ttf) format("truetype")}.katex{text-rendering:auto;font:normal 1.21em KaTeX_Main,Times New Roman,serif;line-height:1.2;text-indent:0}.katex *{-ms-high-contrast-adjust:none!important;border-color:currentColor}.katex .katex-version:after{content:"0.16.2"}.katex .katex-mathml{clip:rect(1px,1px,1px,1px);border:0;height:1px;overflow:hidden;padding:0;position:absolute;width:1px}.katex .katex-html>.newline{display:block}.katex .base{position:relative;white-space:nowrap;width:-webkit-min-content;width:-moz-min-content;width:min-content}.katex .base,.katex .strut{display:inline-block}.katex .textbf{font-weight:700}.katex .textit{font-style:italic}.katex .textrm{font-family:KaTeX_Main}.katex .textsf{font-family:KaTeX_SansSerif}.katex .texttt{font-family:KaTeX_Typewriter}.katex .mathnormal{font-family:KaTeX_Math;font-style:italic}.katex .mathit{font-family:KaTeX_Main;font-style:italic}.katex .mathrm{font-style:normal}.katex .mathbf{font-family:KaTeX_Main;font-weight:700}.katex .boldsymbol{font-family:KaTeX_Math;font-style:italic;font-weight:700}.katex .amsrm,.katex .mathbb,.katex .textbb{font-family:KaTeX_AMS}.katex .mathcal{font-family:KaTeX_Caligraphic}.katex .mathfrak,.katex .textfrak{font-family:KaTeX_Fraktur}.katex .mathtt{font-family:KaTeX_Typewriter}.katex .mathscr,.katex .textscr{font-family:KaTeX_Script}.katex .mathsf,.katex .textsf{font-family:KaTeX_SansSerif}.katex .mathboldsf,.katex .textboldsf{font-family:KaTeX_SansSerif;font-weight:700}.katex .mathitsf,.katex .textitsf{font-family:KaTeX_SansSerif;font-style:italic}.katex .mainrm{font-family:KaTeX_Main;font-style:normal}.katex .vlist-t{border-collapse:collapse;display:inline-table;table-layout:fixed}.katex .vlist-r{display:table-row}.katex .vlist{display:table-cell;position:relative;vertical-align:bottom}.katex .vlist>span{display:block;height:0;position:relative}.katex .vlist>span>span{display:inline-block}.katex .vlist>span>.pstrut{overflow:hidden;width:0}.katex .vlist-t2{margin-right:-2px}.katex .vlist-s{display:table-cell;font-size:1px;min-width:2px;vertical-align:bottom;width:2px}.katex .vbox{align-items:baseline;display:inline-flex;flex-direction:column}.katex .hbox{width:100%}.katex .hbox,.katex .thinbox{display:inline-flex;flex-direction:row}.katex .thinbox{max-width:0;width:0}.katex .msupsub{text-align:left}.katex .mfrac>span>span{text-align:center}.katex .mfrac .frac-line{border-bottom-style:solid;display:inline-block;width:100%}.katex .hdashline,.katex .hline,.katex .mfrac .frac-line,.katex .overline .overline-line,.katex .rule,.katex .underline .underline-line{min-height:1px}.katex .mspace{display:inline-block}.katex .clap,.katex .llap,.katex .rlap{position:relative;width:0}.katex .clap>.inner,.katex .llap>.inner,.katex .rlap>.inner{position:absolute}.katex .clap>.fix,.katex .llap>.fix,.katex .rlap>.fix{display:inline-block}.katex .llap>.inner{right:0}.katex .clap>.inner,.katex .rlap>.inner{left:0}.katex .clap>.inner>span{margin-left:-50%;margin-right:50%}.katex .rule{border:0 solid;display:inline-block;position:relative}.katex .hline,.katex .overline .overline-line,.katex .underline .underline-line{border-bottom-style:solid;display:inline-block;width:100%}.katex .hdashline{border-bottom-style:dashed;display:inline-block;width:100%}.katex .sqrt>.root{margin-left:.27777778em;margin-right:-.55555556em}.katex .fontsize-ensurer.reset-size1.size1,.katex .sizing.reset-size1.size1{font-size:1em}.katex .fontsize-ensurer.reset-size1.size2,.katex .sizing.reset-size1.size2{font-size:1.2em}.katex .fontsize-ensurer.reset-size1.size3,.katex .sizing.reset-size1.size3{font-size:1.4em}.katex .fontsize-ensurer.reset-size1.size4,.katex .sizing.reset-size1.size4{font-size:1.6em}.katex .fontsize-ensurer.reset-size1.size5,.katex .sizing.reset-size1.size5{font-size:1.8em}.katex .fontsize-ensurer.reset-size1.size6,.katex .sizing.reset-size1.size6{font-size:2em}.katex .fontsize-ensurer.reset-size1.size7,.katex .sizing.reset-size1.size7{font-size:2.4em}.katex .fontsize-ensurer.reset-size1.size8,.katex .sizing.reset-size1.size8{font-size:2.88em}.katex .fontsize-ensurer.reset-size1.size9,.katex .sizing.reset-size1.size9{font-size:3.456em}.katex .fontsize-ensurer.reset-size1.size10,.katex .sizing.reset-size1.size10{font-size:4.148em}.katex .fontsize-ensurer.reset-size1.size11,.katex .sizing.reset-size1.size11{font-size:4.976em}.katex .fontsize-ensurer.reset-size2.size1,.katex .sizing.reset-size2.size1{font-size:.83333333em}.katex .fontsize-ensurer.reset-size2.size2,.katex .sizing.reset-size2.size2{font-size:1em}.katex .fontsize-ensurer.reset-size2.size3,.katex .sizing.reset-size2.size3{font-size:1.16666667em}.katex .fontsize-ensurer.reset-size2.size4,.katex .sizing.reset-size2.size4{font-size:1.33333333em}.katex .fontsize-ensurer.reset-size2.size5,.katex .sizing.reset-size2.size5{font-size:1.5em}.katex .fontsize-ensurer.reset-size2.size6,.katex .sizing.reset-size2.size6{font-size:1.66666667em}.katex .fontsize-ensurer.reset-size2.size7,.katex .sizing.reset-size2.size7{font-size:2em}.katex .fontsize-ensurer.reset-size2.size8,.katex .sizing.reset-size2.size8{font-size:2.4em}.katex .fontsize-ensurer.reset-size2.size9,.katex .sizing.reset-size2.size9{font-size:2.88em}.katex .fontsize-ensurer.reset-size2.size10,.katex .sizing.reset-size2.size10{font-size:3.45666667em}.katex .fontsize-ensurer.reset-size2.size11,.katex .sizing.reset-size2.size11{font-size:4.14666667em}.katex .fontsize-ensurer.reset-size3.size1,.katex .sizing.reset-size3.size1{font-size:.71428571em}.katex .fontsize-ensurer.reset-size3.size2,.katex .sizing.reset-size3.size2{font-size:.85714286em}.katex .fontsize-ensurer.reset-size3.size3,.katex .sizing.reset-size3.size3{font-size:1em}.katex .fontsize-ensurer.reset-size3.size4,.katex .sizing.reset-size3.size4{font-size:1.14285714em}.katex .fontsize-ensurer.reset-size3.size5,.katex .sizing.reset-size3.size5{font-size:1.28571429em}.katex .fontsize-ensurer.reset-size3.size6,.katex .sizing.reset-size3.size6{font-size:1.42857143em}.katex .fontsize-ensurer.reset-size3.size7,.katex .sizing.reset-size3.size7{font-size:1.71428571em}.katex .fontsize-ensurer.reset-size3.size8,.katex .sizing.reset-size3.size8{font-size:2.05714286em}.katex .fontsize-ensurer.reset-size3.size9,.katex .sizing.reset-size3.size9{font-size:2.46857143em}.katex .fontsize-ensurer.reset-size3.size10,.katex .sizing.reset-size3.size10{font-size:2.96285714em}.katex .fontsize-ensurer.reset-size3.size11,.katex .sizing.reset-size3.size11{font-size:3.55428571em}.katex .fontsize-ensurer.reset-size4.size1,.katex .sizing.reset-size4.size1{font-size:.625em}.katex .fontsize-ensurer.reset-size4.size2,.katex .sizing.reset-size4.size2{font-size:.75em}.katex .fontsize-ensurer.reset-size4.size3,.katex .sizing.reset-size4.size3{font-size:.875em}.katex .fontsize-ensurer.reset-size4.size4,.katex .sizing.reset-size4.size4{font-size:1em}.katex .fontsize-ensurer.reset-size4.size5,.katex .sizing.reset-size4.size5{font-size:1.125em}.katex .fontsize-ensurer.reset-size4.size6,.katex .sizing.reset-size4.size6{font-size:1.25em}.katex .fontsize-ensurer.reset-size4.size7,.katex .sizing.reset-size4.size7{font-size:1.5em}.katex .fontsize-ensurer.reset-size4.size8,.katex .sizing.reset-size4.size8{font-size:1.8em}.katex .fontsize-ensurer.reset-size4.size9,.katex .sizing.reset-size4.size9{font-size:2.16em}.katex .fontsize-ensurer.reset-size4.size10,.katex .sizing.reset-size4.size10{font-size:2.5925em}.katex .fontsize-ensurer.reset-size4.size11,.katex .sizing.reset-size4.size11{font-size:3.11em}.katex .fontsize-ensurer.reset-size5.size1,.katex .sizing.reset-size5.size1{font-size:.55555556em}.katex .fontsize-ensurer.reset-size5.size2,.katex .sizing.reset-size5.size2{font-size:.66666667em}.katex .fontsize-ensurer.reset-size5.size3,.katex .sizing.reset-size5.size3{font-size:.77777778em}.katex .fontsize-ensurer.reset-size5.size4,.katex .sizing.reset-size5.size4{font-size:.88888889em}.katex .fontsize-ensurer.reset-size5.size5,.katex .sizing.reset-size5.size5{font-size:1em}.katex .fontsize-ensurer.reset-size5.size6,.katex .sizing.reset-size5.size6{font-size:1.11111111em}.katex .fontsize-ensurer.reset-size5.size7,.katex .sizing.reset-size5.size7{font-size:1.33333333em}.katex .fontsize-ensurer.reset-size5.size8,.katex .sizing.reset-size5.size8{font-size:1.6em}.katex .fontsize-ensurer.reset-size5.size9,.katex .sizing.reset-size5.size9{font-size:1.92em}.katex .fontsize-ensurer.reset-size5.size10,.katex .sizing.reset-size5.size10{font-size:2.30444444em}.katex .fontsize-ensurer.reset-size5.size11,.katex .sizing.reset-size5.size11{font-size:2.76444444em}.katex .fontsize-ensurer.reset-size6.size1,.katex .sizing.reset-size6.size1{font-size:.5em}.katex .fontsize-ensurer.reset-size6.size2,.katex .sizing.reset-size6.size2{font-size:.6em}.katex .fontsize-ensurer.reset-size6.size3,.katex .sizing.reset-size6.size3{font-size:.7em}.katex .fontsize-ensurer.reset-size6.size4,.katex .sizing.reset-size6.size4{font-size:.8em}.katex .fontsize-ensurer.reset-size6.size5,.katex .sizing.reset-size6.size5{font-size:.9em}.katex .fontsize-ensurer.reset-size6.size6,.katex .sizing.reset-size6.size6{font-size:1em}.katex .fontsize-ensurer.reset-size6.size7,.katex .sizing.reset-size6.size7{font-size:1.2em}.katex .fontsize-ensurer.reset-size6.size8,.katex .sizing.reset-size6.size8{font-size:1.44em}.katex .fontsize-ensurer.reset-size6.size9,.katex .sizing.reset-size6.size9{font-size:1.728em}.katex .fontsize-ensurer.reset-size6.size10,.katex .sizing.reset-size6.size10{font-size:2.074em}.katex .fontsize-ensurer.reset-size6.size11,.katex .sizing.reset-size6.size11{font-size:2.488em}.katex .fontsize-ensurer.reset-size7.size1,.katex .sizing.reset-size7.size1{font-size:.41666667em}.katex .fontsize-ensurer.reset-size7.size2,.katex .sizing.reset-size7.size2{font-size:.5em}.katex .fontsize-ensurer.reset-size7.size3,.katex .sizing.reset-size7.size3{font-size:.58333333em}.katex .fontsize-ensurer.reset-size7.size4,.katex .sizing.reset-size7.size4{font-size:.66666667em}.katex .fontsize-ensurer.reset-size7.size5,.katex .sizing.reset-size7.size5{font-size:.75em}.katex .fontsize-ensurer.reset-size7.size6,.katex .sizing.reset-size7.size6{font-size:.83333333em}.katex .fontsize-ensurer.reset-size7.size7,.katex .sizing.reset-size7.size7{font-size:1em}.katex .fontsize-ensurer.reset-size7.size8,.katex .sizing.reset-size7.size8{font-size:1.2em}.katex .fontsize-ensurer.reset-size7.size9,.katex .sizing.reset-size7.size9{font-size:1.44em}.katex .fontsize-ensurer.reset-size7.size10,.katex .sizing.reset-size7.size10{font-size:1.72833333em}.katex .fontsize-ensurer.reset-size7.size11,.katex .sizing.reset-size7.size11{font-size:2.07333333em}.katex .fontsize-ensurer.reset-size8.size1,.katex .sizing.reset-size8.size1{font-size:.34722222em}.katex .fontsize-ensurer.reset-size8.size2,.katex .sizing.reset-size8.size2{font-size:.41666667em}.katex .fontsize-ensurer.reset-size8.size3,.katex .sizing.reset-size8.size3{font-size:.48611111em}.katex .fontsize-ensurer.reset-size8.size4,.katex .sizing.reset-size8.size4{font-size:.55555556em}.katex .fontsize-ensurer.reset-size8.size5,.katex .sizing.reset-size8.size5{font-size:.625em}.katex .fontsize-ensurer.reset-size8.size6,.katex .sizing.reset-size8.size6{font-size:.69444444em}.katex .fontsize-ensurer.reset-size8.size7,.katex .sizing.reset-size8.size7{font-size:.83333333em}.katex .fontsize-ensurer.reset-size8.size8,.katex .sizing.reset-size8.size8{font-size:1em}.katex .fontsize-ensurer.reset-size8.size9,.katex .sizing.reset-size8.size9{font-size:1.2em}.katex .fontsize-ensurer.reset-size8.size10,.katex .sizing.reset-size8.size10{font-size:1.44027778em}.katex .fontsize-ensurer.reset-size8.size11,.katex .sizing.reset-size8.size11{font-size:1.72777778em}.katex .fontsize-ensurer.reset-size9.size1,.katex .sizing.reset-size9.size1{font-size:.28935185em}.katex .fontsize-ensurer.reset-size9.size2,.katex .sizing.reset-size9.size2{font-size:.34722222em}.katex .fontsize-ensurer.reset-size9.size3,.katex .sizing.reset-size9.size3{font-size:.40509259em}.katex .fontsize-ensurer.reset-size9.size4,.katex .sizing.reset-size9.size4{font-size:.46296296em}.katex .fontsize-ensurer.reset-size9.size5,.katex .sizing.reset-size9.size5{font-size:.52083333em}.katex .fontsize-ensurer.reset-size9.size6,.katex .sizing.reset-size9.size6{font-size:.5787037em}.katex .fontsize-ensurer.reset-size9.size7,.katex .sizing.reset-size9.size7{font-size:.69444444em}.katex .fontsize-ensurer.reset-size9.size8,.katex .sizing.reset-size9.size8{font-size:.83333333em}.katex .fontsize-ensurer.reset-size9.size9,.katex .sizing.reset-size9.size9{font-size:1em}.katex .fontsize-ensurer.reset-size9.size10,.katex .sizing.reset-size9.size10{font-size:1.20023148em}.katex .fontsize-ensurer.reset-size9.size11,.katex .sizing.reset-size9.size11{font-size:1.43981481em}.katex .fontsize-ensurer.reset-size10.size1,.katex .sizing.reset-size10.size1{font-size:.24108004em}.katex .fontsize-ensurer.reset-size10.size2,.katex .sizing.reset-size10.size2{font-size:.28929605em}.katex .fontsize-ensurer.reset-size10.size3,.katex .sizing.reset-size10.size3{font-size:.33751205em}.katex .fontsize-ensurer.reset-size10.size4,.katex .sizing.reset-size10.size4{font-size:.38572806em}.katex .fontsize-ensurer.reset-size10.size5,.katex .sizing.reset-size10.size5{font-size:.43394407em}.katex .fontsize-ensurer.reset-size10.size6,.katex .sizing.reset-size10.size6{font-size:.48216008em}.katex .fontsize-ensurer.reset-size10.size7,.katex .sizing.reset-size10.size7{font-size:.57859209em}.katex .fontsize-ensurer.reset-size10.size8,.katex .sizing.reset-size10.size8{font-size:.69431051em}.katex .fontsize-ensurer.reset-size10.size9,.katex .sizing.reset-size10.size9{font-size:.83317261em}.katex .fontsize-ensurer.reset-size10.size10,.katex .sizing.reset-size10.size10{font-size:1em}.katex .fontsize-ensurer.reset-size10.size11,.katex .sizing.reset-size10.size11{font-size:1.19961427em}.katex .fontsize-ensurer.reset-size11.size1,.katex .sizing.reset-size11.size1{font-size:.20096463em}.katex .fontsize-ensurer.reset-size11.size2,.katex .sizing.reset-size11.size2{font-size:.24115756em}.katex .fontsize-ensurer.reset-size11.size3,.katex .sizing.reset-size11.size3{font-size:.28135048em}.katex .fontsize-ensurer.reset-size11.size4,.katex .sizing.reset-size11.size4{font-size:.32154341em}.katex .fontsize-ensurer.reset-size11.size5,.katex .sizing.reset-size11.size5{font-size:.36173633em}.katex .fontsize-ensurer.reset-size11.size6,.katex .sizing.reset-size11.size6{font-size:.40192926em}.katex .fontsize-ensurer.reset-size11.size7,.katex .sizing.reset-size11.size7{font-size:.48231511em}.katex .fontsize-ensurer.reset-size11.size8,.katex .sizing.reset-size11.size8{font-size:.57877814em}.katex .fontsize-ensurer.reset-size11.size9,.katex .sizing.reset-size11.size9{font-size:.69453376em}.katex .fontsize-ensurer.reset-size11.size10,.katex .sizing.reset-size11.size10{font-size:.83360129em}.katex .fontsize-ensurer.reset-size11.size11,.katex .sizing.reset-size11.size11{font-size:1em}.katex .delimsizing.size1{font-family:KaTeX_Size1}.katex .delimsizing.size2{font-family:KaTeX_Size2}.katex .delimsizing.size3{font-family:KaTeX_Size3}.katex .delimsizing.size4{font-family:KaTeX_Size4}.katex .delimsizing.mult .delim-size1>span{font-family:KaTeX_Size1}.katex .delimsizing.mult .delim-size4>span{font-family:KaTeX_Size4}.katex .nulldelimiter{display:inline-block;width:.12em}.katex .delimcenter,.katex .op-symbol{position:relative}.katex .op-symbol.small-op{font-family:KaTeX_Size1}.katex .op-symbol.large-op{font-family:KaTeX_Size2}.katex .accent>.vlist-t,.katex .op-limits>.vlist-t{text-align:center}.katex .accent .accent-body{position:relative}.katex .accent .accent-body:not(.accent-full){width:0}.katex .overlay{display:block}.katex .mtable .vertical-separator{display:inline-block;min-width:1px}.katex .mtable .arraycolsep{display:inline-block}.katex .mtable .col-align-c>.vlist-t{text-align:center}.katex .mtable .col-align-l>.vlist-t{text-align:left}.katex .mtable .col-align-r>.vlist-t{text-align:right}.katex .svg-align{text-align:left}.katex svg{fill:currentColor;stroke:currentColor;fill-rule:nonzero;fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:block;height:inherit;position:absolute;width:100%}.katex svg path{stroke:none}.katex img{border-style:none;max-height:none;max-width:none;min-height:0;min-width:0}.katex .stretchy{display:block;overflow:hidden;position:relative;width:100%}.katex .stretchy:after,.katex .stretchy:before{content:""}.katex .hide-tail{overflow:hidden;position:relative;width:100%}.katex .halfarrow-left{left:0;overflow:hidden;position:absolute;width:50.2%}.katex .halfarrow-right{overflow:hidden;position:absolute;right:0;width:50.2%}.katex .brace-left{left:0;overflow:hidden;position:absolute;width:25.1%}.katex .brace-center{left:25%;overflow:hidden;position:absolute;width:50%}.katex .brace-right{overflow:hidden;position:absolute;right:0;width:25.1%}.katex .x-arrow-pad{padding:0 .5em}.katex .cd-arrow-pad{padding:0 .55556em 0 .27778em}.katex .mover,.katex .munder,.katex .x-arrow{text-align:center}.katex .boxpad{padding:0 .3em}.katex .fbox,.katex .fcolorbox{border:.04em solid;box-sizing:border-box}.katex .cancel-pad{padding:0 .2em}.katex .cancel-lap{margin-left:-.2em;margin-right:-.2em}.katex .sout{border-bottom-style:solid;border-bottom-width:.08em}.katex .angl{border-right:.049em solid;border-top:.049em solid;box-sizing:border-box;margin-right:.03889em}.katex .anglpad{padding:0 .03889em}.katex .eqn-num:before{content:"(" counter(katexEqnNo) ")";counter-increment:katexEqnNo}.katex .mml-eqn-num:before{content:"(" counter(mmlEqnNo) ")";counter-increment:mmlEqnNo}.katex .mtr-glue{width:50%}.katex .cd-vert-arrow{display:inline-block;position:relative}.katex .cd-label-left{display:inline-block;position:absolute;right:calc(50% + .3em);text-align:left}.katex .cd-label-right{display:inline-block;left:calc(50% + .3em);position:absolute;text-align:right}.katex-display{display:block;margin:1em 0;text-align:center}.katex-display>.katex{display:block;text-align:center;white-space:nowrap}.katex-display>.katex>.katex-html{display:block;position:relative}.katex-display>.katex>.katex-html>.tag{position:absolute;right:0}.katex-display.leqno>.katex>.katex-html>.tag{left:0;right:auto}.katex-display.fleqn>.katex{padding-left:2em;text-align:left}body{counter-reset:katexEqnNo mmlEqnNo}

</style>

</head>
<body>
    <div class="content-wrapper">
        <p><font size =6><strong>操作系统原理 实验七</strong>&lt;/fontqi</p>
<h2 id="%E4%B8%AA%E4%BA%BA%E4%BF%A1%E6%81%AF" tabindex="-1">个人信息</h2>
<p>（此部分需补充完整）</p>
<p>【院系】 计算机学院</p>
<p>【专业】 计算机专业</p>
<p>【学号】 22336258</p>
<p>【姓名】 谢炎兵</p>
<h2 id="%E5%AE%9E%E9%AA%8C%E9%A2%98%E7%9B%AE" tabindex="-1">实验题目</h2>
<p>内存管理</p>
<h2 id="%E5%AE%9E%E9%AA%8C%E7%9B%AE%E7%9A%84" tabindex="-1">实验目的</h2>
<ol>
<li>实现二级分页机制，并能够在虚拟机地址空间中进行内存管理，包括内存的申请和释放等。</li>
<li>实现动态分区算法。</li>
<li>实现页面置换算法。</li>
<li>掌握和实现虚拟内存管理技术。</li>
</ol>
<h2 id="%E5%AE%9E%E9%AA%8C%E8%A6%81%E6%B1%82" tabindex="-1">实验要求</h2>
<ol>
<li>实现二级分页机制，进行内存管理</li>
<li>实现动态分区算法</li>
<li>实现页面置换算法</li>
<li>撰写实验报告。</li>
</ol>
<h2 id="%E5%AE%9E%E9%AA%8C%E6%96%B9%E6%A1%88" tabindex="-1">实验方案</h2>
<p>本次实验紧密围绕着内存管理，首先需要我们构造一个位图作为工具，用来标记资源情况，进而利用它构造内存池宏观管理资源。接着，我们利用内存池实现物理内存空间的划分，并安置好用户空间和内核空间，为开启分页机制做铺垫。当我们学习完一级分页和二级分页制度的优势后，我们进入实验的核心，开启二级分页模式，最终实现虚拟地址下的内存管理。在内存分配中，我对原始的分配方式进行修改，采取best-fit方式动态分配内存，而虚拟内存页面置换则采用FIFO算法，可以由具体案例看到。最后则理解虚拟页分配的三步过程和页内存的申请释放过程，构造测试例子来分析虚拟页内存管理的实现是否存在bug。</p>
<h2 id="%E5%AE%9E%E9%AA%8C%E8%BF%87%E7%A8%8B" tabindex="-1">实验过程</h2>
<h3 id="%E5%AE%9E%E9%AA%8C%E4%B8%80%EF%BC%9A" tabindex="-1">实验一：</h3>
<p>首先按照要求，探查内存大小：
<img src="屏幕截图 2024-06-10 145722.png" alt="Alt text">
利用教程所给的1代码可以看到初始可以管理的内存大小为126MB。接下来我们利用src中的代码成功构建了bitmap的资源管理结构，并利用它设计了地址池。利用<code>AddressPoolType</code>作为划分，我们在src中构造出了用于全局内存管理的<code>MemoryManager</code>类，区别用户空间与内核空间，实现物理内存管理。到教程所给的src4中，我们在经历规划页目录表和页表在内存中的位置、初始化、将页目录表的地址写入cr3、将cr0的PG位置1后，开启二级分页机制：
<img src="屏幕截图 2024-06-10 151148.png" alt="Alt text">
此时可以看到我们已经成功实现分页机制，内核地址空间起始位于0x200000，而用户地址空间起始地址为0x4070000,两者平分剩余部分内存空间，各自占据62MB内存。
由于我们尚未详细进入虚拟内存管理，因此这里展示分配和释放物理内存的过程，首先构造一个线程，直接调用<code>allocatePhysicalPages</code>和<code>releasePhysicalPages</code>观察内存分配前后变化，具体测试代码如下：</p>
<pre class='hljs'><code><div>void first_thread(void *arg)
{
    // 第1个线程不可以返回
    // stdio.moveCursor(0);
    // for (int i = 0; i &lt; 25 * 80; ++i)
    // {
    //     stdio.print(' ');
    // }
    // stdio.moveCursor(0);
    char *curry = (char *)memoryManager.allocatePhysicalPages(AddressPoolType::USER, 200);
    char *poole = (char *)memoryManager.allocatePhysicalPages(AddressPoolType::USER, 100);
    printf(&quot;curry's start address is %x\n&quot;, curry);
    printf(&quot;curry's start address is %x\n&quot;, poole);
    memoryManager.releasePhysicalPages(AddressPoolType::USER, (int)curry, 200);
    memoryManager.releasePhysicalPages(AddressPoolType::USER, (int)poole, 100);
    asm_halt();
}
</div></code></pre>
<p>由于release函数是void函数不会返回任何值，因此我们同样在<code>releasePhysicalPages</code>作出了小修改，使其得以在成功执行后输出反馈，结果如下图：
<img src="屏幕截图 2024-06-10 155657.png" alt="Alt text">
此时可以看到curry和poole都成功申请到了地址，并且经过计算，4138000-4070000=C8000（16进制），转10进制为：819200，除以4096正好为200，正是我们所分配给curry的页数，说明实验成功。</p>
<h3 id="%E5%AE%9E%E9%AA%8C%E4%BA%8C%EF%BC%9A" tabindex="-1">实验二：</h3>
<p>在本次实验中，我们需要参照理论课上的学习的物理内存分配算法实现动态分区算法，在具体的分区上，很容易想到只有bitmap和地址池会涉及这样的操作，自然的，想实现动态分区算法也该从它们入手。由于具体分配资源是用bitmap实现的，因此我们只需要修改bitmap分配资源的方式即可。由于教程已经实现了First-fit的方法，这里我采用其他的方法，Best-fit方法，找到剩余空间中最小的可放置申请内存块的空间，具体代码如下：</p>
<pre class='hljs'><code><div>int BitMap::allocate(const int count)
{
    if (count == 0)
        return -1;
    int best_index=-1, best_size=4096*15*1000;  //由于分配的内存不可能超过62MB，因此任意选一个极大的数作为开始情况即可
    int index = 0;
    while (index &lt; length)
    {
        // 越过已经分配的资源
        while (index &lt; length &amp;&amp; get(index))
            ++index;
        // 不存在连续的count个资源
        if (index == length)
            return -1;
        int temp_size=0;   //考虑当前大小，开始计数，并且将当前index暂时保存
        int temp_id=index;
        while ((index &lt; length) &amp;&amp; (!get(index)))
        {
            ++temp_size;
            ++index;
        }      
        if(temp_size &gt;= count &amp;&amp; temp_size &lt; best_size)
        {
            //更新现在最优解
            best_size=temp_size;
            best_index=temp_id;
        }        
    }   
    if(best_index!=-1)
    {
        for(int i=0; i&lt;count; i++)
        {
            set(best_index + i, true);
        }
    }
    return best_index;  //如果没有找到合适的块，best_index会返回-1，否则是一个有意义的值。
}
</div></code></pre>
<p>分析一下代码复杂度，由于每次都要对整个位图进行遍历，因此复杂度为O（n），这里n已经确定了，因此可以认为是常数时间。由于使用的是Best-fit方法，因此每次都会找到最优的一个小块进行内存分配，不过这种算法也会带来比较多的内存碎片。</p>
<p>为了验证算法起到作用，我们构造4个申请内存块的任务，大小依次为500,400,300,200，并将第1个和第3个任务内存释放，并再引入一个任务，申请的内存块为200，根据Best-fit算法，此时新任务最优放置的地方是原本第3个任务的地址，即2和4之间的“孔”，情况如下图：
<img src="微信图片_20240610164938-1.jpg" alt="Alt text">
接下来观看程序输出的结果：
<img src="屏幕截图 2024-06-10 164515.png" alt="Alt text">
可以发现gwen和wiggins的内存申请地址是一样的，符合我们的预期，实验成功。</p>
<h3 id="%E5%AE%9E%E9%AA%8C%E4%B8%89%EF%BC%9A" tabindex="-1">实验三：</h3>
<p>在虚拟内存管理中，页面置换是指当系统需要为新的数据分配物理内存空间，而现有的物理内存已满时，系统会选择将一部分物理内存中的页面暂时移至磁盘上的交换区，以释放物理内存空间。
参照理论课上虚拟内存管理的页面置换算法实现页面置换，这里我实现的是FIFO算法。考虑到页面置换建立后不会再出现申请内存被拒绝的情况（即函数返回-1或0这样的值），我们首先考虑<code>MemoryManager::allocatePages(enum AddressPoolType type, const int count)</code>这个函数是否是需要核心修改的函数。现实生活中，我们通常遇到的情况是虚拟内存比实际内存大得多，也就是说虚拟内存申请一般不会失败，而物理内存则是我们需要考虑的，因此需要解决的冲突是物理内存不够，然而在本次实验中，虚拟内存和物理内存大小相等，并且虚拟内存总要求连续，因此虚拟内存不够是我们主要考虑的。
具体实现上，由于还没有实现动态分配内存，不太清楚指针会分配到哪里，因此这里我们构造了一个先进先出的固定队列，长度为20000，代表最多可以容纳20000个申请（事实上完全足够了，根据后续实现来看，申请最多为15984），每个申请用结构体MemoryBlock表示，具体数据结构为：</p>
<pre class='hljs'><code><div>struct MemoryBlock
{
    //起始地址start_address，内存块大小count
     int start_address, count;
};

class MemoryBlockQueue
{
private:
    //队列的头索引front, 尾索引rear
     int front, rear;
    //用于实现队列的数组，大小足够大即可
    MemoryBlock memoryBlocks[20000];

public:
    //初始化函数
    void initialize();
    //队列的push函数，参数为内存块的起始地址和大小
    void push(int address, int count);
    //队列的pop函数，返回一个内存块结构体
    MemoryBlock pop_front();
};
</div></code></pre>
<p>实现先进先出主要需要构建好push和pop功能，具体代码为：</p>
<pre class='hljs'><code><div>void MemoryBlockQueue::initialize()
{
    //初始化，当头尾指针相等时代表当前队列为空
    front = 0;
    rear = 0;
}

void MemoryBlockQueue::push(int address, int count)
{
    //依次赋值，更新尾指针
    memoryBlocks[rear].start_address = address;
    memoryBlocks[rear].count = count;
    rear++;
    rear %= 20000;
}

MemoryBlock MemoryBlockQueue::pop_front()
{
    //弹出时利用头指针弹出
    front++;
    front %= 20000;
    if(!front) 
    return memoryBlocks[19999];  //注意边界条件
    else return memoryBlocks[front-1]; 
}
</div></code></pre>
<p>队列的操作基本都大同小异，数据结构课已经操作很多次了，具体看一看分配页的过程。由于页面置换已经开启，我们不再会出现分配不到内存的状况，因此首要变革的就是虚拟内存分配，既要保证其存在又要保证其连续。为了实现上述要求，我们必须在虚拟内存不足时利用先进先出函数pop出内存块，pop一个空间不够时再继续pop，直到虚拟内存腾出足够空间为止，具体代码修改如下：</p>
<pre class='hljs'><code><div>int MemoryManager::allocatePages(enum AddressPoolType type, const int count)
{
    // 第一步：从虚拟地址池中分配若干虚拟页
    int virtualAddress = allocateVirtualPages(type, count);
    while (!virtualAddress)
    {
            //在内存块队列中pop出位置最前的一个内存块
            MemoryBlock block = kernelMemoryBlocks.pop_front();
            //输出即将被释放的内存块的起始地址和大小
            printf(&quot;Trigger page replacement and release virtual blocks,\nrelease address starts at 0x%x now I will release %d page(s)\n &quot;,        block.start_address, block.count);
            //释放虚拟内存
            releasePages(type, block.start_address, block.count);
            //再次申请内存，内存分配失败则继续删除虚拟内存
            virtualAddress = allocateVirtualPages(type, count);
            printf(&quot;my virtualAddress is %x\n&quot; ,virtualAddress);
    }
    //申请成功后将该内存块push到内存块队列中
    kernelMemoryBlocks.push(virtualAddress, count);
    bool flag;
    int physicalPageAddress;
    int vaddress = virtualAddress;

    // 依次为每一个虚拟页指定物理页
    for (int i = 0; i &lt; count; ++i, vaddress += PAGE_SIZE)
    {
        flag = false;
        // 第二步：从物理地址池中分配一个物理页
        physicalPageAddress = allocatePhysicalPages(type, 1);
        if (physicalPageAddress)
        {
            //printf(&quot;allocate physical page 0x%x\n&quot;, physicalPageAddress);

            // 第三步：为虚拟页建立页目录项和页表项，使虚拟页内的地址经过分页机制变换到物理页内。
            flag = connectPhysicalVirtualPage(vaddress, physicalPageAddress);
        }
        else
        {
            flag = false;
        }

        // 分配失败，释放前面已经分配的虚拟页和物理页表
        if (!flag)
        {
            // 前i个页表已经指定了物理页
            releasePages(type, virtualAddress, i);
            // 剩余的页表未指定物理页
            releaseVirtualPages(type, virtualAddress + i * PAGE_SIZE, count - i);
            printf(&quot;Oh no, something wrong!\n&quot;);
            return 0;
        }
    }

    return virtualAddress;
}
</div></code></pre>
<p>比较特别的是，我仍然保留了物理内存分配失败的函数用于检测页面置换是否事实上完成而非只在虚拟内存上完成，这在特殊情况下会有反馈，具体原因稍后再说。
现在前期的准备已经完成，接下来进入测试用例的构建：</p>
<pre class='hljs'><code><div>void first_thread(void *arg)
{
    // 第1个线程不可以返回
    // stdio.moveCursor(0);
    // for (int i = 0; i &lt; 25 * 80; ++i)
    // {
    //     stdio.print(' ');
    // }
    // stdio.moveCursor(0);

    char *p1 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 7992);
    printf(&quot;%x\n&quot;, p1);
    char *p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 799);
    printf(&quot;%x\n&quot;, p2);
    char *p3 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 7991);
    printf(&quot;%x\n&quot;, p3);
    printf(&quot;%x %x %x\n&quot;, p1, p2, p3);

    //printf(&quot;%x\n&quot;, p3);

    char *p4 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 7300);
    
    printf(&quot;%x\n&quot;, p4);

    asm_halt();
}
</div></code></pre>
<p>结果如图所示：
<img src="屏幕截图 2024-06-12 090231.png" alt="alt text">
可以看到，在放入大小为7992和799大小的虚拟内存块后，再放入大小为7991大小的块空间不足了，因此会将先前的7992大小块换出，此时程序输出“Trigger page replacement”，从新分配的虚拟地址来看，它成功替换了原本块，起始地址为0xc0100000。当我们再试图放入大小为7300的块时，又一次触发了页面置换，大小为799的块被换出，程序新分配的地址为0xc2037000,正好是799地址0xc2038000的上一页（十进制即4096），说明其被正好替换腾出足够空间，实验符合预期。</p>
<h5 id="%E5%AE%9E%E9%AA%8C%E4%B8%89%E7%9A%84%E8%A1%A5%E5%85%85%EF%BC%9A" tabindex="-1">实验三的补充：</h5>
<p>此时为了解释前面我为什么要保留分配失败的函数的判断，需要回顾虚拟内存空间和物理内存空间的关系。以实验操作涉及的内核空间为例，物理内核空间至少有两页为页目录表和0到1MB映射所需的页表，此外还涉及254个有具体含义不可随意赋值的页表。不仅如此，在后续分配物理空间时，其对应的页表也会放在物理内核空间，占据了一部分内存，所以虚拟内核空间实际上是比物理内核空间可操作的空间更大的。在这种情况下，为虚拟内存申请15984个内存页就是不可能的，以及15983,15982等等都会失败，因此检验物理内存分配的函数还是有必要存在的。
下面可见一个小例子，如果在测试中试图分配15984个虚拟内存页：
<img src="屏幕截图 2024-06-12 093425.png" alt="alt text">
可以看到，尽管触发了页面置换，却还是输出了&quot;Oh no, something wrong!&quot;，符合我们的预期。</p>
<h3 id="%E5%AE%9E%E9%AA%8C%E5%9B%9B%EF%BC%9A" tabindex="-1">实验四：</h3>
<p>本实验主要需要我们分析虚拟内存管理的流程，并构造一些测试用例来检验教程代码的正确性。
1、页内存分配。页内存分配主要分为三步，首先需要从虚拟地址池中分配若干连续的虚拟页，这部分比较简单，利用<code>allocateVirtualPages(type, count)</code>函数实现，如果成功则返回一个虚拟内存地址，否则则返回0，从而将内存抽象为程序员眼中连续的部分。第二步需要对每一个虚拟页，从物理地址池中分配1页。这需要对于指定的count数目的页，利用<code>physicalPageAddress = allocatePhysicalPages(type, 1)</code>来对虚拟内存进行一一分配，如此以来便可实现物理空间上的离散化，不受连续性制约。第三步是为虚拟页建立页目录项和页表项，使虚拟页内的地址经过分页机制变换到物理页内。这里利用的是<code>connectPhysicalVirtualPage(vaddress, physicalPageAddress)</code>函数，将虚拟内存与刚刚分配的物理内存建立具体联系，填好页目录表和页表项，在此函数内需要调用<code>toPDE(const int virtualAddress)</code>和<code>toPTE(const int virtualAddress)</code>函数，首先从内核物理地址空间中分配一个页表，再利用pde和pte信息使页目录项指向页表，初始化页表，使页表项指向物理页，实现页内存分配。值得注意的是，在没有实现页面置换功能前，我们应当考虑分配虚拟内存不成功的情况，进行内存释放，避免内存泄漏。
2、页内存释放。页内存释放需要同时考虑虚拟内存的释放和物理内存的释放，两者只要有一样没有被同时释放就会导致资源的永久性丢失，相应的内存空间无法再利用。页内存的释放分为两个过程，首先对每一个虚拟页，释放为其分配的物理页。为了找到这个物理页，我们需要一个将虚拟内存地址转化为物理内存地址的函数，<code>MemoryManager::vaddr2paddr(int vaddr)</code>通过调用<code>toPTE(vaddr)</code>得到pte信息，经过处理得到最终的物理内存地址<code>(page + offset)</code>,有了物理内存地址我们就可以对连续的count项虚拟内存地址顺利进行转化并释放。第二步则是释放虚拟页，释放虚拟页的函数为<code>MemoryManager::releaseVirtualPages(enum AddressPoolType type, const int vaddr, const int count)</code>，其函数实现方式与物理页释放函数相当接近，底层原理都只需要调用地址池相关函数。比较需要我们注意的是，物理页释放后，函数会接着清除相应的页表项，确保这部分内存不会被错误地访问或重新分配而未清零。为此，它将页表项设置为0，即标记这些虚拟页不再映射任何物理页，如此更严谨地保障了内存不会泄露。
最后构造一个简单的测试用例来展现具体效果，代码为：</p>
<pre class='hljs'><code><div>void first_thread(void *arg)
{
    // 第1个线程不可以返回
    char *p1 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
    char *p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
    char *p3 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
    printf(&quot;%x %x %x\n&quot;, p1, p2, p3);
    memoryManager.releasePages(AddressPoolType::KERNEL, (int)p2, 10);
    p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
    printf(&quot;%x\n&quot;, p2);
    p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
    
    printf(&quot;%x\n&quot;, p2);

    asm_halt();
}
</div></code></pre>
<p>效果图：
<img src="屏幕截图 2024-06-10 225014.png" alt="Alt text">
可以看到程序首先输出了p1,p2,p3的内核虚拟地址，并在每次释放p2再申请p2时输出新的内核虚拟地址。注意到最后一行输出的c0164000与第一次的p2输出完全一致，与第二次则不同，说明原本的虚拟内存释放成功，并因为算法机制再次申请到了原本的地址，实验符合我们的预期。</p>
<h2 id="%E5%AE%9E%E9%AA%8C%E6%80%BB%E7%BB%93" tabindex="-1">实验总结</h2>
<p>在本次实验中，我们从无到有来构造一个简单的内存管理系统，刚开始时先了解了位图对于资源分配的作用，再循序渐进，逐渐构建出了地址池，并用地址池管理物理内存空间。当前期准备充足后，我们打开了二级分页机制，引入用户虚拟地址空间，用户物理地址空间，内核虚拟地址空间，内核物理地址空间等概念，跟随教程学习虚拟内存的管理，包括虚拟页分配、虚拟页释放，并在要求下动手实现虚拟页置换方法，从而对整个内存管理操作有了直观的认识。这次的实验的确是本学期以来我遇到过的最有挑战性的实验，说实话许多概念仍然处于朦朦胧胧的状态，大致知道整体思路是什么，每段代码作用是什么，但是想用自己的语言把整个过程捋顺依然需要时间。在这次实验中，比较需要花时间消化的是构造虚拟内存的页目录项和页表项，由于CPU总会对程序内的地址进行三部分拆分解读来获取物理地址，因此页目录表和页表项的内容需要精心设计，从而让CPU解读地址得到的物理地址达到我们期望的含义，其转化的过程有一种“虚拟的虚拟”的意义，初次接触比较还是比较绕的。此外，理清物理内存和虚拟内存的大小关系以及具体地址装的是什么是非常重要的，在结合教材理解各种概念后会让实践轻松很多，这提醒我们要重视在课堂上打好根基。总体来说，这次实验紧密围绕着课本第八章和第九章的内容，让我们得以将实验与理论结合。同时，我也更感受到虚拟内存的思想的魅力，尽管其实现的代价很大，但它成功实现了让普通程序员将内存视作线性的愿望，甚至允许我们使用比物理内存大得多的假想资源，从而在现代计算机系统中得到广泛应用。这次的实验深化了我对计算机系统理解，也拓宽了我的知识面，让我受益匪浅。</p>
<h2 id="%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE" tabindex="-1">参考文献</h2>
<p>（如有要列出，包括网上资源）</p>

    </div>
</body>
</html>
